---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.10.3
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

+++ {"slideshow": {"slide_type": "slide"}}

# Big Number Conversion

+++ {"slideshow": {"slide_type": "-"}, "tags": ["remove-cell"]}

**CS1302 Introduction to Computer Programming**
___

```{code-cell} ipython3
from math import floor, log2
```

+++ {"slideshow": {"slide_type": "slide"}}

## Conversion to Decimal

+++ {"slideshow": {"slide_type": "subslide"}}

In this notebook, we will use iterations to convert numbers with arbitrary size.

+++ {"slideshow": {"slide_type": "subslide"}}

### Binary-to-Decimal

+++ {"slideshow": {"slide_type": "fragment"}}

In a previous lab, we considered converting a byte string to decimal. What about converting a binary string of arbitrary length to decimal?

+++ {"slideshow": {"slide_type": "subslide"}}

````{prf:definition} Binary numbers

Given a binary string of an arbitrarily length $k$,

$$ 
b_{k-1}\circ \dots \circ b_1\circ b_0,
$$
the decimal number is given by the formula

$$
2^0 \cdot b_0 + 2^1 \cdot b_1 + \dots + 2^{k-1} \cdot b_{k-1}.
$$ (b2d:1)

````

+++ {"slideshow": {"slide_type": "fragment"}}

In mathematics, we use the summation notation to write the above formula {eq}`b2d:1`:

$$ 
\sum_{i=0}^{k-1} 2^i \cdot b_{i}.
$$ (b2d:2)

+++ {"slideshow": {"slide_type": "subslide"}}

In a program, the formula can be implemented as a for loop:

```{code-cell} ipython3
def binary_to_decimal_v1(binary_str):
    k = len(binary_str)
    decimal = 0  # initialization
    for i in range(k):
        decimal += 2 ** i * int(binary_str[(k - 1) - i])  # iteration
    return decimal
```

+++ {"slideshow": {"slide_type": "fragment"}}

Note that $b_i$ is given by `binary_str[(k-1)-i]` for different index `i` as shown below:

$$
\begin{array}{c|c:c:c:c|}\texttt{binary_str} & b_{k-1} & b_{k-2} & \dots & b_0\\ \text{indexing} & [0] & [1] & \dots & [k-1] \end{array}
$$

+++ {"slideshow": {"slide_type": "subslide"}}

The following is another way to write the for loop.

```{code-cell} ipython3
def binary_to_decimal_v2(binary_str):
    decimal = 0  # initialization
    for bit in binary_str:
        decimal = decimal * 2 + int(bit)  # iteration
    return decimal
```

+++ {"slideshow": {"slide_type": "fragment"}}

The algorithm implements the same formula factorized as follows:

$$
\begin{aligned} \sum_{i=0}^{k-1} 2^i \cdot b_{i} 
&=  \left(\sum_{i=1}^{k-1} 2^i \cdot b_{i}\right) + b_0\\
&=  \left(\sum_{i=1}^{k-1} 2^{i-1} \cdot b_{i}\right)\times 2 + b_0 \\
&=  \left(\sum_{j=0}^{k-2} 2^{j} \cdot b_{j+1}\right)\times 2 + b_0 && \text{with $j=i-1$} \\
&= \underbrace{(\dots (\underbrace{(\underbrace{\overbrace{0}^{\text{initialization}\kern-2em}\times 2 + b_{k-1}}_{\text{first iteration} }) \times 2 + b_{k-2}}_{\text{second iteration} }) \dots )\times 2 + b_0}_{\text{last iteration} }.\end{aligned}
$$ (b2d:3)

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Write your own converter `binary_to_decimal` below. Make it as efficient as possible.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: f1e194aff055633aead3f89c8047a17a
  grade: false
  grade_id: binary_to_decimal
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def binary_to_decimal(binary_str):
    # YOUR CODE HERE
    raise NotImplementedError()
    return decimal
```

````{hint}

You can choose one of the two implementations above but take the time to type in the code instead of copy-and-paste.

````

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 91fc75df3ab7d19f958f9c774d809914
  grade: true
  grade_id: test-binary_to_decimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [hide-input, remove-output]
---
# tests
import numpy as np


def test_binary_to_decimal(decimal, binary_str):
    decimal_ = binary_to_decimal(binary_str)
    correct = isinstance(decimal_, int) and decimal_ == decimal
    if not correct:
        print(f"{binary_str} should give {decimal} not {decimal_}.")
    assert correct


test_binary_to_decimal(0, "0")
test_binary_to_decimal(255, "11111111")
test_binary_to_decimal(52154, "1100101110111010")
test_binary_to_decimal(3430, "110101100110")
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 4021762033790ce89b1b10c76cbe7dae
  grade: true
  grade_id: hidden_test-binary_to_decimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

```{code-cell} ipython3
---
code_folding: [0]
slideshow:
  slide_type: '-'
tags: [remove-output]
---
# binary-to-decimal converter
from ipywidgets import interact

bits = ["0", "1"]


@interact(binary_str="1011")
def convert_byte_to_decimal(binary_str):
    for bit in binary_str:
        if bit not in bits:
            print("Not a binary string.")
            break
    else:
        print("decimal:", binary_to_decimal(binary_str))
```

+++ {"slideshow": {"slide_type": "slide"}}

### Undecimal-to-Decimal

+++ {"slideshow": {"slide_type": "fragment"}}

A base-11 number system is called an [undecimal system](https://en.wikipedia.org/wiki/Undecimal). The digits range from 0 to 10 with 10 denoted as X:

$$
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X.
$$

The [International Standard Book Number (ISBN)](https://en.wikipedia.org/wiki/International_Standard_Book_Number) uses an undecimal digit.

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** In the following code, assign to `decimal` the integer represented by an undecimal string of arbitrary length.  

+++ {"slideshow": {"slide_type": "-"}}

````{hint}

Write a conditional to 
1. check if a digit is (capital) `'X'`, and if so, 
2. convert the digit to the integer value 10.

````

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: 55bbfbe8143ad30f684efd927989183e
  grade: false
  grade_id: undecimal_to_decimal
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: subslide
tags: [remove-output]
---
def undecimal_to_decimal(undecimal_str):
    # YOUR CODE HERE
    raise NotImplementedError()
    return decimal
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: af19b56f1f1c98807e67e6ab8829606a
  grade: true
  grade_id: test-undecimal_to_decimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [hide-input, remove-output]
---
# tests
def test_undecimal_to_decimal(decimal, undecimal_str):
    decimal_ = undecimal_to_decimal(undecimal_str)
    correct = isinstance(decimal_, int) and decimal_ == decimal
    if not correct:
        print(f"{undecimal_str} should give {decimal} not {decimal_}.")
    assert correct


test_undecimal_to_decimal(27558279079916281, "6662X0X584839464")
test_undecimal_to_decimal(23022771839270, "73769X2556695")
test_undecimal_to_decimal(161804347284488, "476129248X2067")
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: da072224351c55417d95cad1736e15af
  grade: true
  grade_id: hidden_test-undecimal_to_decimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

```{code-cell} ipython3
---
code_folding: [0]
slideshow:
  slide_type: '-'
tags: [remove-output]
---
# undecimal-to-decimal calculator
from ipywidgets import interact

undecimal_digits = [str(i) for i in range(10)] + ["X"]


@interact(undecimal_str="X")
def convert_undecimal_to_decimal(undecimal_str):
    for digit in undecimal_str:
        if digit not in undecimal_digits:
            print("Not an undecimal string.")
            break
    else:
        print("decimal:", undecimal_to_decimal(undecimal_str))
```

+++ {"slideshow": {"slide_type": "slide"}}

## Conversion from Decimal

+++ {"slideshow": {"slide_type": "fragment"}}

Consider the reverse process that converts a non-negative decimal number of arbitrary size to a string representation in another number system.

+++ {"slideshow": {"slide_type": "subslide"}}

### Decimal-to-Binary

+++ {"slideshow": {"slide_type": "subslide"}}

The following code converts a decimal number to a binary string.

+++ {"slideshow": {"slide_type": "-"}}

```Python
def decimal_to_binary(decimal):
    binary_str = str(decimal % 2)
    while decimal // 2:
        decimal //= 2
        binary_str = str(decimal % 2) + binary_str
    return binary_str
```

+++ {"slideshow": {"slide_type": "fragment"}}

To understand the while loop, consider the same formula {eq}`b2d:3`, where the braces indicate the value of `decimal` at different times:

$$
\begin{aligned} \sum_{i=0}^{k-1} 2^i \cdot b_{i} &=  \left(\sum_{i=0}^{k-2} 2^{i-2} \cdot b_{i-1}\right)\times 2 + b_0 \\
&= \underbrace{(\underbrace{ \dots (\underbrace{(0\times 2 + b_{k-1}) \times 2 + b_{k-2}}_{\text{right before the last iteration} }  )\times 2 \dots + b_1}_{\text{right before the second iteration} })\times 2 + b_0}_{\text{right before the first iteration} }.\end{aligned}
$$ 

+++ {"slideshow": {"slide_type": "fragment"}}

- $b_0$ is the remainder `decimal % 2` right before the first iteration,
- $b_1$ is the remainder `decimal // 2 % 2` right before the second iteration, and
- $b_{k-1}$ is the remainder `decimal // 2 % 2` right before the last iteration.

+++ {"slideshow": {"slide_type": "fragment"}}

We can also write a for loop instead of a while loop:

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
---
def decimal_to_binary(decimal):
    binary_str = ""
    num_bits = 1 + (decimal and floor(log2(decimal)))
    for i in range(num_bits):
        binary_str = str(decimal % 2) + binary_str
        decimal //= 2
    return binary_str
```

```{code-cell} ipython3
---
code_folding: [0]
slideshow:
  slide_type: '-'
tags: [remove-output]
---
# decimal-to-binary calculator
@interact(decimal="11")
def convert_decimal_to_binary(decimal):
    if not decimal.isdigit():
        print("Not a non-negative integer.")
    else:
        print("binary:", decimal_to_binary(int(decimal)))
```

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Explain what the expression `1 + (decimal and floor(log2(decimal)))` calculates. In particular, explain the purpose of the logical `and` operation in the expression?

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "12d1969b35591f01fcf2478d720b06aa", "grade": true, "grade_id": "number-of-bits", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false}, "slideshow": {"slide_type": "-"}}

YOUR ANSWER HERE

+++ {"slideshow": {"slide_type": "slide"}}

### Decimal-to-Undecimal

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Assign to `undecimal_str` the undecimal string that represents a non-negative integer `decimal` of any size.

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
nbgrader:
  cell_type: code
  checksum: 701b02e9f4258346bf3709536abd9661
  grade: false
  grade_id: decimal_to_undecimal
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def decimal_to_undecimal(decimal):
    # YOUR CODE HERE
    raise NotImplementedError()
    return undecimal_str
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: af7198d1334cca1f1b3e7cbef25622e4
  grade: true
  grade_id: test-decimal_to_undecimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [hide-input, remove-output]
---
# tests
def test_decimal_to_undecimal(undecimal, decimal):
    undecimal_ = decimal_to_undecimal(decimal)
    correct = isinstance(undecimal, str) and undecimal == undecimal_
    if not correct:
        print(
            f"{decimal} should be represented as the undecimal string {undecimal}, not {undecimal_}."
        )
    assert correct


test_decimal_to_undecimal("X", 10)
test_decimal_to_undecimal("0", 0)
test_decimal_to_undecimal("1752572309X478", 57983478668530)
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: e824531a2ae5e3112d2cb45ea8a244d2
  grade: true
  grade_id: hidden_test-decimal_to_undecimal
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

```{code-cell} ipython3
---
code_folding: [0]
slideshow:
  slide_type: '-'
tags: [remove-output]
---
# undecimal-to-decimal calculator
from ipywidgets import interact


@interact(decimal="10")
def convert_decimal_to_undecimal(decimal):
    if not decimal.isdigit():
        print("Not a non-negative integer.")
    else:
        print("undecimal:", decimal_to_undecimal(int(decimal)))
```

## Timer (Optional)

+++

### Benchmark

+++

Recall the two versions of binary-to-decimal converters defined at the beginning of the lab:

```{code-cell} ipython3
binary_to_decimal_v1??
```

```{code-cell} ipython3
binary_to_decimal_v2??
```

**How to compare their speed?**

+++

We can use the [time](https://docs.python.org/3/library/time.html) module.

```{code-cell} ipython3
import time

time.localtime()
```

We can also [format](https://docs.python.org/3/library/time.html#time.strftime) the current [local time](https://docs.python.org/3/library/time.html#time.localtime) to a more easily readable string:

```{code-cell} ipython3
:tags: []

time.strftime("%a, %d %b %Y %H:%M:%S", time.localtime())
```

**How to implement a timer?**

+++

The idea is to record the start time and end time, and then compute their difference:

```{code-cell} ipython3
start = time.localtime()
...  # code to be timed
end = time.localtime()
end - start
```

Unfortunately, the above code fails because `-` is note defined for the time object `time.struct_time`.

+++

**How to compute the difference in time?**

+++

Instead of implementing `-` for `time.struct_time`, a simpler solution is to use [`time.time()`](https://docs.python.org/3/library/time.html#time.time), which returns the current time as a floating point number.

```{code-cell} ipython3
time.time()
```

This is the number of *seconds* elapsed after certain [epoch](https://docs.python.org/3/library/time.html#epoch) (a point in time). For linux/unix, the `time` module uses the [unix epoch](https://en.wikipedia.org/wiki/Unix_time), which is January 1, 1970, 00:00:00 ([UTC](https://en.wikipedia.org/wiki/Coordinated_Universal_Time)):

```{code-cell} ipython3
time.strftime(
    "%a, %d %b %Y %H:%M:%S +0000 ", time.gmtime(0)
)  # Convert zero seconds to UTC time
```

The following code implements the timer:

```{code-cell} ipython3
def time_b2d(binary_to_decimal, binary_str):
    """Return the time in secs for running binary_to_decimal on binary_str."""
    start = time.time()
    decimal = binary_to_decimal(binary_str)
    end = time.time()
    return end - start
```

In the following, `t1` and `t2` keeps the time it takes for `binary_to_decimal_v1` and `binary_to_decimal_v2` to run on the same input byte `binary_str`.

```{code-cell} ipython3
:tags: [remove-output]

if input("Ready? [Y/n]").lower() != "n":
    binary_str = "1" * 8
    t1 = time_b2d(binary_to_decimal_v1, binary_str)
    t2 = time_b2d(binary_to_decimal_v2, binary_str)
    print(f"t1 = {t1:.3g}s\nt2 = {t2:.3g}s\nt1/t2 = {t1/t2:.3g}")
```

**Exercise** (Optional) Observe the difference in speeds for longer `binary_str`, e.g., with `binary_str = '1' * 100000`. Is the ratio `t1/t2` of the running times roughly the same regardless of the input length?

+++

There can be variations in the running time due to many factors. To measure the typical performance, we should run the code multiple times and report the total or average running time. The following is the modified timer:

```{code-cell} ipython3
:tags: []

def time_b2d(binary_to_decimal, binary_str, n_iters):
    """Return the time in secs for running binary_to_decimal on binary_str."""
    start = time.time()
    for i in range(n_iters):
        decimal = binary_to_decimal(binary_str)
    end = time.time()
    return end - start
```

To compare:

```{code-cell} ipython3
:tags: [remove-output]

if input("Ready? [Y/n]").lower() != "n":
    binary_str = "1" * 8
    n_iters = 100
    t1 = time_b2d(binary_to_decimal_v1, binary_str, n_iters)
    t2 = time_b2d(binary_to_decimal_v2, binary_str, n_iters)
    print(f"t1 = {t1:.3g}s\nt2 = {t2:.3g}s\nt1/t2 = {t1/t2:.3g}")
```

**Exercise** (Optional) Increase the number of iterations until you get can a variation in `t1/t2` less than 0.2 in two consecutive runs most of the time.

+++

Indeed, IPython has a [built-in magic](https://ipython.readthedocs.io/en/stable/interactive/magics.html#magic-timeit) to time an execution:

```{code-cell} ipython3
%%timeit
binary_to_decimal_v1("1" * 8)
```

```{code-cell} ipython3
%%timeit
binary_to_decimal_v2("1" * 8)
```

Note that the numbers of loops are decided automatically.

+++

### Alarm clock

+++

**How to set an alarm in python to go off after certain time?**

+++

We can write a loop like the following:

```{code-cell} ipython3
:tags: [remove-output]

duration = int(input("How many seconds to wait?"))
start = time.time()
while time.time() - start <= duration:
    pass
print("Time's up!")
```

A simpler way is to use `time.sleep`:

```{code-cell} ipython3
:tags: [remove-output]

time.sleep(int(input("How many seconds to wait?")))
time.sleep?
```

**How to play a sound when time is up?**

+++

To play a beep sound in jupyter notebook, we can use the `jupyter_beeper` module:

```{code-cell} ipython3
:tags: [remove-output]

import jupyter_beeper

beeper = jupyter_beeper.Beeper()


def alarm(seconds):
    time.sleep(seconds)
    beeper.beep()
```

To set the alarm to 3 seconds after now:

```{code-cell} ipython3
:tags: [remove-output]

alarm(int(input("How many seconds to wait?")))
```

Notice that the alarm is blocking the execution. To avoid that, we need to run it as a [thread](https://docs.python.org/3/library/threading.html):

```{code-cell} ipython3
import threading


def background_alarm(seconds):
    threading.Thread(target=alarm, args=(seconds,)).start()
```

To set two alarms simultaneously:

```{code-cell} ipython3
:tags: [remove-output]

background_alarm(int(input("How many seconds to wait?")))
background_alarm(int(input("How many seconds to wait?")))
```

**Exercise** (Optional) Modify `alarm` to give 3 consecutive beeps in 1 second interval after a duration (in seconds) specified by the user.